#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Comparer {
public:
    Comparer (const string& string) : text(string) {};

    bool operator() (int i, int j) {
        string tmp = text.substr(i, text.length() - 1);
        return tmp.compare(text.substr(j, text.length() - 1)) < 0;
    }
private:
    string text;
};

void initSuffixArray (const string& text, vector<int>& suffixArray) {
    size_t textLength = text.length();
    for (size_t i = 0; i < textLength; ++i)
        suffixArray[i] = i;
    sort(suffixArray.begin(), suffixArray.end(), Comparer(text));
}

void searchString(const vector<int>& suffixArray, const string& text, const string& subString, int left, int right, int mLeft = 0, int mRight = 0) {
    int cLeft = left, cRight = right, mlr = min(mLeft, mRight), cmp = 0;
    while (cLeft <= cRight) {
        int middle = (cLeft + cRight) / 2, n = min(text.length() - suffixArray[middle] - mlr, subString.length() - mlr);
        int i = suffixArray[middle] + mlr, j = mlr, count = 0;
        while (count < n) {
            if(text[i] == subString[j])
                ++count;
            else 
                break;
            ++i; ++j;
        }
        cmp = (count == n) ? 0 : ((subString[j] < text[i]) ? (count > 0 ? count : 1) : (count > 0 ? -count : -1));
        if (!cmp && count > 0) {
            searchString(suffixArray, text, subString, left, middle - 1, mLeft, mlr);
            cout << suffixArray[middle] << " ";
            searchString(suffixArray, text, subString, middle + 1, right, mlr, mRight);
            return;
        } else {
            if (count > 0)
                mlr += abs(cmp);
            if (cmp > 0)
                cRight = middle - 1;
            else
                cLeft = middle + 1;
        }
    }
}

int main()
{
    string text;
    ifstream ifile("in2.txt");
    if (getline(ifile, text)) {
        vector<int> suffixArray(text.length());
        initSuffixArray(text, suffixArray);
        string subString;
        while (getline(ifile, subString))
            if(!subString.empty()) {
                cout << subString << ": ";
                searchString(suffixArray, text, subString, 0, text.length() - 1);
                cout << endl;
            }
    }
    ifile.close();
    return 0;
}